// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-20 13:20
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.ArraysTrain;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum {
    /**
     * 找出数组中所有和为0而且不重复的组合
     * 双指针
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int n = nums.length, cur = 0;
        for (int p = 0; p < n - 2; p++) {
            if (p > 0 && nums[p] == nums[p - 1]) {
                continue;
            }
            cur = nums[p] + nums[n - 1] + nums[n - 2];
            if (cur < 0) {
                continue;
            }
            cur = nums[p] + nums[p + 1] + nums[p + 2];
            if (cur > 0) {
                break;
            }
            int h = p + 1, t = n - 1;
            while (h < t) {
                cur = nums[p] + nums[h] + nums[t];
                if (cur == 0) {
                    res.add(Arrays.asList(nums[p], nums[h], nums[t]));
                    h++;
                    while (h < t && nums[h] == nums[h - 1]) {
                        h++;
                    }
                    t--;
                    while (h < t && nums[t] == nums[t + 1]) {
                        t--;
                    }
                } else if (cur > 0) {
                    t--;
                } else {
                    h++;
                }
            }
        }
        return res;
    }
}
